package com.cat.dynamicPlanning;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/interleaving-string/
 * @create 2025/8/31 11:19
 * @since JDK17
 */

public class Solution32 {
    public boolean isInterleave(String s11, String s22, String s33) {
        char[] s1 = s11.toCharArray(), s2 = s22.toCharArray(), s3 = s33.toCharArray();
        int n = s1.length, m = s2.length, o = s3.length;
        if (n + m < o) {
            return false;
        }
        boolean [][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;
        for (int i = 1; i < m; i++) {
            if (s2[i - 1] != s3[i - 1]) {
                break;
            }
            dp[0][i] = true;
        }
        for (int i = 1; i < n; i++) {
            if (s1[i - 1] != s3[i - 1]) {
                break;
            }
            dp[i][0] = true;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = (s1[i - 1] == s3[i + j - 1] && dp[i - 1][j]) || (s2[j - 1] == s3[i + j - 1] && dp[i][j - 1]);
                if (i + j == o && dp[i][j]) {
                    return true;
                }
            }
        }
        return false;
    }
}
